//
// Created by jyc on 2021/10/3.
//

#ifndef IMGUI_EXAMPLE_GLFW_VULKAN_DIRECTEDGRAPHTRAVERSAL_H
#define IMGUI_EXAMPLE_GLFW_VULKAN_DIRECTEDGRAPHTRAVERSAL_H

#include "DirectedGraph.h"
#include <stack>
namespace Bonnie{
    class DirectedGraphTopologicalSort{
    public:
        static std::vector<uint32_t> sort(DirectedGraph * pGraph){
            auto ts = DirectedGraphTopologicalSort(pGraph);
            for (int i = 0; i < pGraph->getCurrentNodeId(); ++i) {
                auto pNode = pGraph->getNode(i);
                if(pNode && ts.mVisited[i] == false){
                    ts.sortInternal(i);
                }
            }
            std::vector<uint32_t> result;
            auto& s = ts.mStack;
            result.reserve(s.size());
            while (!s.empty()) {
                result.push_back(s.top());
                s.pop();
            }
            return result;
        }

    private:
        DirectedGraphTopologicalSort(DirectedGraph* pGraph): mpGraph(pGraph),mVisited(pGraph->getCurrentNodeId(),false){};
        DirectedGraph* mpGraph;
        std::stack<uint32_t> mStack;
        std::vector<uint32_t >mVisited;
        void sortInternal(uint32_t node){
            if (mVisited[node])
                return;
            mVisited[node] = true;
            for (int i = 0; i < mpGraph->getNode(node)->getOutcomeEdgeCount(); ++i) {
                auto edgeIdx = mpGraph->getNode(node)->getOutcomeEdge(i);
                auto edge = mpGraph->getEdge(edgeIdx);
                assert(edge != nullptr);    // the edge  links two existed node
                sortInternal(edge->getDestNode());
            }
            if (mpGraph->getNode(node)->getOutcomeEdgeCount() == 0 && mpGraph->getNode(node)->getIncomeEdgeCount() == 0)
                return;
            mStack.push(node);
        }
    };
}

#endif //IMGUI_EXAMPLE_GLFW_VULKAN_DIRECTEDGRAPHTRAVERSAL_H
